Test Adjacency - Educational Content

Comparing the cost of checking if two vertices are connected.

With a set-based Adjacency List, checking for an edge `(u, v)` means searching `v` in `adj[u]`. This takes time proportional to `u`'s degree, $O(\deg(u))$, but is near $O(1)$ on average for sets.
With an Adjacency Matrix, the check is a direct lookup at `A[u,v]`. This is a true constant-time operation, $O(1)$, which is its main advantage for dense graphs.

Python: Adjacency Test Functions

def adjacent_list(adj,u,v):
    return v in adj[u]

def adjacent_matrix(A,i,j):
    return bool(A[i][j])